struct OldDriverTree {
	using i64 = long long;
	struct node {
		node(int l, int r, i64 v) : l_(l), r_(r), v_(v) {}

		bool operator<(const node& other) const {
			return l_ < other.l_;
		}

		int l_, r_;
		mutable i64 v_;
	};
	using SIT = set<node>::iterator;
		
	SIT split(int p) {
		SIT it = tr_.lower_bound({p, 0, 0});
		if (it != tr_.end() && it->l_ == p) {
			return it;
		}
		--it;
		auto [tl, tr, tv] = *it;
		tr_.erase(it);
		tr_.emplace(tl, p - 1, tv);
		return tr_.emplace(p, tr, tv).first;
	}

	void assign(int l, int r, i64 v) {
		SIT itr = split(r + 1), itl = split(l);
		tr_.erase(itl, itr);
		tr_.emplace(l, r, v);
	}

	void add(int l, int r, i64 v) {
		SIT itr = split(r + 1), itl = split(l);
		for (auto it = itl; it != itr; it++) {
			it->v_ += v;
		}
	}

	i64 kth(int l, int r, int k) {
		assert(k <= r - l + 1);
		vector<pair<i64, int>> rank;
		SIT itr = split(r + 1), itl = split(l);
		for (auto it = itl; it != itr; it++) {
			rank.emplace_back(it->v_, it->r_ - it->l_ + 1);
		}
		sort(rank.begin(), rank.end());
		for (auto [v, c] : rank) {
			k -= c;
			if (k <= 0) {
				return v;
			}
		}
	}

	// 求区间k次幂和
	int query(const int l, const int r, const int k, const int mod) {
		SIT itr = split(r + 1), itl = split(l);
		i64 sum = 0;
		for (auto it = itl; it != itr; it++) {
			sum = (sum + (i64)(it->r_ - it->l_ + 1) * power(it->v_, k, mod) % mod) % mod;
		}
		return sum;
	}

	i64 power(i64 a, int b, int mod) {
		int result = 1;
		a %= mod;
		for (; b > 0; b >>= 1) {
			if (b & 1) {
				result = (result * a) % mod;
			}
			a = 1ll *  a * a % mod;
		}
		return result;
	}

	void insert(int l, int r, i64 v) {
		tr_.emplace(l, r, v);
	}
	set<node> tr_;
};
OldDriverTree odt;
// 注意添加最后一个位置+1的位置，否则可能会Re
void init() {
	int n = 1e5, v = 1e5;
	for (int i = 1; i <= n; i++) odt.insert(i, i, v);
  odt.insert(n + 1, n + 1, 0);
}